package com.lwt.codetop.dp;
// 5. 最长回文子串

/**
 * 找出一个字符串的最长回文子串。 回文串具有对称性，围绕这个对称性解题。
 * 思路一：区间DP, f[i][j]：子串s[i~j]是否为回文串
 *        长度为1都为true
 *        长度>=2：s[i][j]为回文串当且仅当 s[i] == s[j] && f[i+1][j-1] == true
 * 思路二：中心扩散法，即双指针
 *        回文串有奇数和偶数的情况，分开讨论，然后选择最长的作为答案即可。
 */
public class LongestPalindromicSubstring {
    public static void main(String[] args) {
        // 构建测试用例
        String s = "babad";
        int n = s.length();
        s = " " + s; // 下标从1开始
        String res = "";

//        boolean[][] f = new boolean[n + 10][n + 10];
//        // 区间dp
//        for(int len = 1; len <= n; len ++){
//            for(int i = 1; i + len - 1 <= n; i ++){// 枚举区间左端点
//                int j = i + len - 1;
//                if(len == 1){
//                    f[i][j] = true;
//                }else{ // len >= 2
//                    if(s.charAt(i) == s.charAt(j) && (len == 2 || f[i + 1][j - 1] == true)){
//                        f[i][j] = true;
//                    }
//                }
//                // 更新答案，求最长回文串
//                if(f[i][j] == true && len > res.length()){
//                    res = s.substring(i, j + 1); // [i, j)
//                }
//            }
//        }

        // 中心=扩散法则
        for(int i = 1; i <= n; i ++){
            // 回文串是偶数的情况
            int l = i, r = i + 1;
            while(l >= 1 && r <= n && s.charAt(l) == s.charAt(r)){
                l -= 1;
                r += 1;
            }
            // 更新答案
            if(r - l - 1 > res.length()) res = s.substring(l + 1, r);

            // 回文串是奇数的情况
            l = i - 1; r = i + 1;
            while(l >= 1 && r <= n && s.charAt(l) == s.charAt(r)){
                l -= 1;
                r += 1;
            }
            // 更新答案
            if(r - l - 1 > res.length()) res = s.substring(l + 1, r);
        }

        System.out.println(res);
    }
}
